Queue

Introduction#

The queue is a data structure that works under the first-in-first-out (FIFO) principle. The first element added to the queue would be the first to be deleted and so on.

Applications of queue#

Queues are used in a variety of applications, including:

• Scheduling of shared resources in the operating system.
• Multiprogramming tasks.
• Message queue of a messaging service.
• Breadth-first search (BFS) of trees and graphs.

Let’s look at ADT operations of queues.

Queue ADT operations#

• Add(k) adds an element k at the end of the queue.
• Remove() removes the first element from the queue and returns its value.
• Front() returns the first element of the queue.
• Size() returns the number of elements in the queue.
• IsEmpty() checks whether the queue is empty or not. If the queue is empty, it returns true. Otherwise, it returns false.

Note: All of the above queue operations are implemented in $O(1)$ time complexity.

The illustration below demonstrates what a queue looks like.

Example#

Queues are implemented in Go as follows:

    We’ll learn about queues in detail in a later chapter.